public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.search(new int[]{4,5,6,7,0,1,2}, 0));
        System.out.println(s.search(new int[]{4,5,6,7,0,1,2}, 3));
        System.out.println(s.search(new int[]{1}, 0));
    }
}


class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while(lo <= hi){
            int mid = (lo + hi) / 2;

            //普通有序数列
            if(nums[lo] <= nums[mid] && nums[mid] <= nums[hi]){
                if(nums[mid] > target){
                    hi = mid - 1;
                }
                else if(nums[mid] < target) {
                    lo = mid + 1;
                }
                else{
                    return mid;
                }
                continue;
            }

            //旋转的数列, mid在旋转前为左部分
            if(nums[lo] >= nums[mid] && nums[mid] <= nums[hi]){
                if(nums[mid] > target){
                    hi = mid - 1;
                }
                else if (nums[mid] < target){
                    if(target <= nums[hi]){
                        lo = mid + 1;
                    }
                    else{
                        hi = mid - 1;
                    }
                }
                else{
                    return mid;
                }
                continue;
            }

            //旋转的数列，mid在旋转前为右部分
            if(nums[lo] <= nums[mid] && nums[mid] >= nums[hi]){
                if(nums[mid] < target){
                    lo = mid + 1;
                }
                else if(nums[mid] > target){
                    if(nums[lo] <= target){
                        hi = mid - 1;
                    }
                    else{
                        lo = mid + 1;
                    }
                }
                else{
                    return mid;
                }
            }
        }

        return -1;
    }
}